1
Python 列表的物理真相：ArrayList 内存布局与寻址
AI028 Lesson 8
00:00

Python 列表在底层并非松散的链表，而是高度组织化的 ArrayList。其核心真相是：它在内存中占据一段连续的地址空间。这里存储的不是对象本身，而是指向对象的 引用（在 C 语言层面即为指针）。这种设计实现了异构数据的统一管理，无论是三原色（RGB）元组还是复杂的加密密钥 (Key)，都只需占据一个固定大小的指针位。

Ptr 0 Ptr 1 Ptr 3 元素搬迁 (Insert)

寻址数学与性能权衡

  • $O(1)$ 随机访问：通过公式 $\text{元素地址} = \text{起始地址} + \text{下标} \times \text{大小}$，CPU 可瞬间定位。
  • 均摊分析 (Amortized Analysis)：利用过度分配策略，虽然单次插入可能 $O(n)$，但 $\text{总代价} = n + \sum_{j=0}^{\lg n} 2^j = 3n$，确保了均摊 $O(1)$ 的追加性能。
  • 插入限制：如 Figure 8-2 所示，在任意位置 `insert` 必须平移后续所有指针，复杂度为 $O(n)$。
算法对照
与 ArrayList 的索引（$O(1)$）不同，跳表 (Skip List) 的搜索操作时间复杂度是 $O(\log n)$。而 RSA 算法的基础——欧几里得算法，其核心在于 $gcd(a,0)=a$。这些算法都在内存的这片方寸之地运行。